Nella maggior parte delle discipline scientifiche (ad esempio fisica, chimica, biologia...) per stabilire la verità di un’affermazione si ricorre a misurazioni, esperimenti o simulazioni: se gli esperimenti, magari fatti più volte e da più persone, confermano l’affermazione questa viene accettata (almeno temporaneamente), altrimenti viene rifiutata.
Esempio: il principio di Archimede Ogni corpo immerso parzialmente o completamente in un fluido riceve una spinta verticale dal basso verso l’alto, uguale per intensità al peso del volume del fluido spostato.
In matematica (ma anche in informatica), questo “metodo scientifico” non funziona!
Ad esempio, nessun esperimento potrà mai stabilire se \(\sqrt{2}\) sia un numero razionale (ovvero se \(\sqrt{2} = \frac{n}{m}\) con \(n\) ed \(m\) numeri interi).
Controllare alcuni casi specifici (= misurazioni, esperimenti o simulazioni) può essere utile per avere indizi sulla verità o meno di un’affermazione, ma a volte questi indizi possono anche essere fuorvianti. Vediamo un esempio...
\(991 \cdot n^2 + 1\) non è mai un quadrato perfetto (ovvero la sua radice quadrata non è un numero intero).
Si è dimostrato che tale congettura è falsa, anzi ci sono infiniti numeri del tipo \(991 \cdot n^2 +1\) che sono quadrati perfetti. Tuttavia, il più piccolo di tali numeri è
\(\mathbf{12055735790331359447442538767} \approx\) \(1,2 \cdot 10^{28} >\) diametro terra
Quanto è grande questo numero?
Diametro terra: \(\approx\) \(6,371 \cdot 10^{6}\) m
\(\mathbf{12055735790331359447442538767} \approx\) \(1,2 \cdot 10^{28} >\) diametro sole
Quanto è grande questo numero?
Diametro sole: \(\approx\) \(1,39 \cdot 10^9\) m
\(\mathbf{12055735790331359447442538767} \approx\) \(1,2 \cdot 10^{28} >\) distanza terra-sole
Quanto è grande questo numero?
Distanza terra-sole: \(\approx\) \(1,5 \cdot 10^{11}\) m
\(\mathbf{12055735790331359447442538767} \approx\) \(1,2 \cdot 10^{28} >\) età dell’universo
Quanto è grande questo numero?
Età dell’universo: \(\approx\) \(13,83 \cdot 10^9\) m
\(\mathbf{12055735790331359447442538767} \approx\) \(1,2 \cdot 10^{28} >\) numero di stelle
Quanto è grande questo numero?
Numero di stelle nell’universo osservabile: \(\approx\) \(3 \cdot 10^{23}\)
\(\mathbf{12055735790331359447442538767} \approx\) \(1,2 \cdot 10^{28} >\) cellule umane
Quanto è grande questo numero?
Cellule che compongono tutti gli esseri umani messi insieme: \(\approx\) \(10^{24}\) m
\(\mathbf{12055735790331359447442538767} \approx\) \(1,2 \cdot 10^{28}\)
Quanto è grande questo numero? Confrontatelo con il numero di stelle nell’universo osservabile, ovvero: \(\approx\) \(3 \cdot 10^{23}\) . Il nostro numero è enorme!
Quindi controllare a mano la congettura con degli esempi (anche moltissimi!) ci avrebbe erroneamente indotti a crederla vera...
In matematica, per stabilire la verità di un’affermazione (= teorema) si deve ricorrere a una dimostrazione.
Teorema: è l’affermazione (riguardante numeri, funzioni, enti geometrici, o altri oggetti matematici) che si vuole dimostrare. Di solito è della forma
“Se valgono certe ipotesi, allora anche la tesi del teorema è vera.”
Esempio: Se \(p\) e \(q\) sono numeri negativi, allora \(p \cdot q\) è un numero positivo.
Dimostrazione: catena di ragionamenti che ci permette di concludere che la tesi del teorema deve essere vera partendo dall’assunzione che le ipotesi del teorema siano vere.
La stessa cosa vale in informatica. Supponiamo di aver scritto il programma che controlla la ventilazione di una sonda spaziale. Verificare con un certo numero (anche elevatissimo!) di esperimenti o simulazioni che il programma non va in crash ed esegue correttamente tutte le operazioni che deve svolgere non è sufficiente...
Come si può garantire che una volta in funzione sulla sonda spaziale non si verifichi proprio una situazione, mai incontrata nelle simulazioni, che porti al blocco del sistema (per la gioia degli astronauti presenti a bordo, che morirebbero soffocati)?
L’unico modo è fornire una dimostrazione del fatto che il programma funziona, ovvero della sua correttezza. Pur parlando di programmi e non di numeri, il concetto di dimostrazione è esattamente lo stesso usato in matematica quando si parla di teoremi. In questo caso il teorema sarà
Teorema Il programma è corretto.
Un teorema è un enunciato della forma
Se valgono \(\mathrm{P}_{1}\) e \(\mathrm{P}_{2}\) e …\(\mathrm{P}_{n}\), allora vale anche \(\mathrm{Q}\).
Le affermazioni \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) sono dette ipotesi del teorema, mentre \(\mathrm{Q}\) è detta tesi del teorema.
Un esempio di teorema è il seguente:
Teorema Se \(n\) è un numero naturale dispari ed \(m\) è un numero naturale pari, allora \(n + m\) è dispari.
Teorema
Se \(\underbrace{\text{ n è un numero naturale dispari}}_{\mathrm{P}_{1}}\) ed \(\underbrace{\text{ m è un numero naturale pari}}_{\mathrm{P}_{2}}\), allora \(\underbrace{\text{n + m è dispari}}_{\mathrm{Q}}\).
In questo caso le ipotesi sono
\(n\) è un numero naturale dispari,
\(m\) è un numero naturale pari,
mentre la tesi è
\(n + m\) è dispari.
In matematica sono di uso comune anche altri sinonimi di “Teorema”, ad esempio “Proposizione”, “Lemma” e così via.
Dal punto di vista tecnico, tutti questi termini vogliono dire esattamente la stessa cosa, ovvero che quel che si sta affermando è un teorema.
La differenza tra le varie espressioni è l’importanza (del tutto soggettiva!) che chi scrive o parla vuole attribuire all’affermazione che si sta dimostrando: solitamente si riserva il termine “Teorema” per quelle che si ritengono veramente importanti e significative, “Proposizione” per quelle che sono un po’ meno importanti ma pur sempre abbastanza significative e “Lemma” per quelle affermazioni che di per sé non sarebbero molto significative, ma che servono poi per dimostrare altri fatti più importanti.
Quando si analizza il ragionamento matematico, come faremo noi in questo corso, non si tiene conto di queste distinzioni e si parla sempre di teorema.
Il teorema
Se valgono \(\mathrm{P}_{1}\), \(\mathrm{P}_{2}\), …, \(\mathrm{P}_{n}\), allora vale anche \(\mathrm{Q}\).
intende asserire che:
In qualunque contesto o situazione le affermazioni \(\mathrm{P}_{1}\), \(\mathrm{P}_{2}\), … \(\mathrm{P}_{n}\) sono verificate, anche l’affermazione \(\mathrm{Q}\) risulta essere vera.
Utilizzeremo la scrittura \[\mathrm{P}_{1},\dotsc,\mathrm{P}_{n}\models \mathrm{Q}\] (che si legge “\(\mathrm{Q}\) è conseguenza logica di \(\mathrm{P}_{1}\),…, \(\mathrm{P}_{n}\)”) per tradurre in un linguaggio simbolico il teorema con ipotesi \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) e tesi \(\mathrm{Q}\).
Ci sono anche affermazioni \(\mathrm{Q}\) che sono valide in qualunque contesto, ossia enunciati per i quali \[\models \mathrm{Q}\] è un teorema che non ha bisogno di ipotesi.
Ad esempio
Lo zero è il più piccolo tra i numeri naturali.
Un’affermazione \(\mathrm{Q}\) di questo tipo viene detta tautologia.
Stabilire che cosa sia un contesto/situazione in cui sia possibile valutare se una data affermazione \(\mathrm{P}\) sia vera o falsa è molto delicato (buona parte del corso sarà dedicata a dare una formulazione rigorosa di cosa siano questi “contesti”).
Negli esempi seguenti tutti le affermazioni \(\mathrm{P}\) che considereremo parleranno di numeri \(n,m,x\): i “contesti” possibili saranno allora tutti i possibili valori che questi numeri possono assumere.
L’affermazione “\(n\) è un numero naturale dispari” è vera nella situazione in cui \(n\) vale \(3\), ma falsa quando \(n\) vale \(4\).
Come possiamo organizzare in modo rigoroso un ragionamento e stabilire che esso costituisce la dimostrazione di un teorema?
Ci sono diverse strategie dimostrative variamente utilizzate (spesso in combinazione tra loro). Nel seguito presenteremo le più comuni ossia:
la dimostrazione diretta,
la dimostrazione per assurdo,
la dimostrazione per contrapposizione,
la dimostrazione per composizione (o interpolazione),
la dimostrazione per casi.
Vedremo nella Sezione 1.3 che la correttezza di tutte queste strategie dimostrative può essere verificata in maniera rigorosa utilizzando la logica proposizionale.
La dimostrazione diretta è la strategia più semplice e naturale per stabilire un teorema del tipo \[\mathrm{P}_{1},\dots,\mathrm{P}_{n}\models \mathrm{Q}.\]
La dimostrazione diretta assume di trovarsi in un qualunque contesto in cui siano verificate le ipotesi \(\mathrm{P}_{1},\dots,\mathrm{P}_{n}\) e sulla base di semplici e rigorosi ragionamenti stabilisce che in tale contesto anche la tesi \(\mathrm{Q}\) è verificata.
Se \(n\) è un numero intero dispari e \(m\) è un numero intero pari, allora \(n + m\) è un numero intero dispari.
Siano \(n\) ed \(m\) interi qualsiasi, e assumiamo che \(n\) sia dispari ed \(m\) pari, ovvero che \(n = 2 l + 1\) per qualche intero \(l\), mentre \(m = 2 k\) per qualche intero \(k\). Bisogna dimostrare che \(n + m\) è dispari. Effettuando i calcoli si ha:
| \( n + m \) | \( = ( 2 l + 1 ) + 2k \) |
| \( = ( 2 l + 2 k ) + 1 \) | |
| \( = 2 ( l + k ) + 1 \) |
Dimostrazione per assurdo Una dimostrazione per assurdo di una proposizione \(\mathrm{Q}\) a partire dalle ipotesi \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) è una dimostrazione in cui si assume che \(\mathrm{Q}\) sia falsa e da questa assunzione si deriva (utilizzando anche le ipotesi \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\)) una contraddizione, ovvero una proposizione della forma
\(\mathrm{R}\) e non \(\mathrm{R}\)
che asserisce che una qualche affermazione \(\mathrm{R}\) è al contempo sia vera che falsa. Poiché una contraddizione è necessariamente falsa (una proposizione in un dato contesto può essere vera o falsa, ma non entrambe contemporaneamente!), questo prova che assumere che \(\mathrm{Q}\) sia falsa porta a conclusioni assurde, e quindi \(\mathrm{Q}\) non può che essere vera. In altre parole: si dimostra che se le premesse \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) sono vere non è possibile che \(\mathrm{Q}\) sia falsa.
Una dimostrazione con questa struttura viene anche chiamata una dimostrazione indiretta.
Concretamente, in una dimostrazione per assurdo di un teorema del tipo \[\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\] si assume che le ipotesi \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) siano vere ma che, per assurdo, la tesi \(\mathrm{Q}\) sia falsa, e da questa assunzione si deriva una contraddizione.
Quando invece il teorema è del tipo \[\models \mathrm{Q},\] ovvero quando si deve dimostrare \(\mathrm{Q}\) senza partire da alcuna ipotesi (cioè quando bisogna mostrare che \(\mathrm{Q}\) è una tautologia), allora una dimostrazione per assurdo consiste semplicemente nell’assumere per assurdo che \(\mathrm{Q}\) sia falsa, e poi dimostrare che da quest’assunzione deriva una contraddizione.
Per tutti i numeri reali \(x , y\), se \(\underbrace{ x+y \geq 2 }_{\mathrm{P}}\) allora \(\underbrace{ x \geq 1 \text{ oppure } y \geq 1}_{\mathrm{Q}}\).
Siano \(x\) e \(y\) numeri reali qualsiasi, e supponiamo per assurdo che \(\mathrm{P}\) sia vera ma \(\mathrm{Q}\) sia falsa, ovvero che valgano \(x+y \geq 2\) e \(x,y < 1\).
(Si osservi che assumere che “\(x \geq 1\) oppure \(y \geq 1\)” sia falsa è equivalente ad assumere che “\(x < 1\) e \(y < 1\)” sia vera.)
Dalla negazione di \(\mathrm{Q}\) segue che \(x + y < 1 + 1\), ovvero \(x+y < 2\). Ma questo contraddice l’assunzione \(\mathrm{P}\), ovvero si avrebbe che
\(x+y \geq 2\) e non \(x+y \geq 2\).
Questo dimostra (per assurdo) che se vale \(\mathrm{P}\) allora \(\mathrm{Q}\) non può essere falsa. In altre parole, è vero che se vale \(\mathrm{P}\) allora deve valere anche \(\mathrm{Q}\), quindi il teorema è dimostrato.
Dimostriamo ora l’enunciato:
Per ogni numero intero \(n\), se \(\underbrace{ n^2 \text{ è pari}}_{\mathrm{P}}\), allora \(\underbrace{ n \text{ è pari}}_{\mathrm{Q}}\).
Supponiamo per assurdo che \(\mathrm{P}\) sia vera ma \(\mathrm{Q}\) sia falsa (ovvero che \(n\) sia dispari) e facciamo vedere che queste assunzioni portano ad una contraddizione. Sia \(n\) dispari, ovvero \(n = 2m + 1\) per qualche intero \(m\). Allora possiamo calcolare:
| \( {n^2} \) | \( = (2m + 1)^2 \) |
| \( = 4m^2 + 4m + 1 \) | |
| \( = 2(2m^2 + 2m) + 1, \) |
“\(n^2\) è pari” e non “\(n^2\) è pari”,
contraddizione! Quindi se vale \(\mathrm{P}\) deve valere anche \(\mathrm{Q}\).
Introduciamo una tecnica che può essere utilizzata per semplificare la dimostrazione che abbiamo appena visto.
Per dimostrare un teorema del tipo \(\mathrm{P}\) \(\models\) \(\mathrm{Q}\), si può anche dimostrare (in modo diretto) il teorema:
non \(\mathrm{Q} \models\) non \(\mathrm{P}\).
Infatti, supponiamo di aver stabilito la correttezza del teorema “non \(\mathrm{Q} \models\) non \(\mathrm{P}\)” e di essere in un contesto in cui vale l’ipotesi \(\mathrm{P}\). Allora in tale contesto anche \(\mathrm{Q}\) deve essere vera, perché se fosse falsa (ovvero se valesse “non \(\mathrm{Q}\)”) allora si avrebbe che sia \(\mathrm{P}\) (per ipotesi) che “non \(\mathrm{P}\)” (per il teorema non \(\mathrm{Q} \models\) non \(\mathrm{P}\)) sarebbero vere, contraddizione!
Posto di sapere che non \(\mathrm{Q} \models\) non \(\mathrm{P}\), questo argomento mostra che in ogni contesto in cui valga \(\mathrm{P}\) deve valere anche \(\mathrm{Q}\), ossia che \(\mathrm{P}\models \mathrm{Q}\).
Se \(n^2\) è un numero intero pari allora \(n\) è un numero intero pari.
dimostrando (in modo diretto) l’enunciato:
Se \(\underbrace{n~\text{è un numero intero dispari}}_{(n \text{ non è pari})}\) allora \(\underbrace{n^2~\text{è dispari}}_{( n^2 \text{ non è pari})}\).
Se \(\underbrace{n~\text{è un numero intero dispari}}_{( n \text{ non è pari})}\) allora \(\underbrace{ n^2~\text{è dispari}}_{( n^2 \text{ non è pari})}\).
Assumiamo che \(n\) sia dispari, ovvero che \(n = 2k+1\) per qualche intero \(k\): bisogna dimostrare allora che anche \(n^2\) è dispari. Svolgendo i calcoli si ha che
| \( n^2 \) | \( = (2k+1)^2 \) |
| \( = (4k^2+4k+1) \) | |
| \(= 2(2k^2+2k)+1 \) |
Se abbiamo dimostrato il teorema \[\mathrm{P}_{1},\dotsc,\mathrm{P}_{n}\models \mathrm{Q}\] ed il teorema \[\mathrm{Q}\models \mathrm{R},\]
allora possiamo comporre le due dimostrazioni in una dimostrazione di \[\mathrm{P}_{1},\dotsc,\mathrm{P}_{n} \models \mathrm{R}\] nel modo seguente:
In ogni contesto in cui valgano le ipotesi \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) deve valere anche \(\mathrm{Q}\) , dato che \(\mathrm{P}_{1},\dots,\mathrm{P}_{n}\models \mathrm{Q}\). Ma allora in tale contesto deve valere anche \(\mathrm{R}\) poiché \(\mathrm{Q}\models \mathrm{R}\). Quindi abbiamo stabilito che in ogni contesto in cui valgano \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) anche \(\mathrm{R}\) deve valere, ossia che \(\mathrm{P}_{1},\dots,\mathrm{P}_{n}\models \mathrm{R}\).
Se \(\underbrace{ n \text{ è un numero intero dispari}}_{\mathrm{P}_{1}}\) e \(\underbrace{ m \text{ è un numero intero pari}}_{\mathrm{P}_{2}}\) allora \(\underbrace{(n + m)^2 \text{ è un numero intero dispari}}_{\mathrm{R}}\).
Abbiamo visto in precedenza che considerando \[\underbrace{(n + m) \text{ è un numero intero dispari}}_{\mathrm{Q}},\] si ha che \(\mathrm{P}_{1}\),\(\mathrm{P}_{2}\)\(\models\) \(\mathrm{Q}\) e \(\mathrm{Q}\)\(\models\)\(\mathrm{R}\). Componendo le dimostrazioni dei due teoremi otteniamo quindi una dimostrazione di \(\mathrm{P}_{1}\),\(\mathrm{P}_{2}\)\(\models\) \(\mathrm{R}\).
Dimostrazione per casi Quando si deve dimostrare un teorema della forma \(\mathrm{P}\) \(\models\) \(\mathrm{Q}\) dove \(\mathrm{P}\) è una disgiunzione di enunciati della forma
\(\mathrm{P}_{1}\) oppure \(\mathrm{P}_{2}\) oppure …oppure \(\mathrm{P}_{n}\),
conviene dimostrare separatamente i teoremi
Infatti, supponiamo di aver dimostrato ciascuno dei teoremi sopra elencati. Se in un contesto vale \(\mathrm{P}\), in questo contesto almeno un \(\mathrm{P}_{j}\) tra i \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) sarà vero, per cui avendo dimostrato che \(\mathrm{P}_{j}\) \(\models\) \(\mathrm{Q}\) possiamo concludere che in tale contesto anche \(\mathrm{Q}\) è vero.
A volte i “casi” \(\mathrm{P}_{1}, \dotsc , \mathrm{P}_{n}\) non sono esplicitamente dati dall’enunciato, ma possiamo comunque distinguere diversi casi nella dimostrazione (quando questo è utile).
Ad esempio, per dimostrare un teorema \(\models \mathrm{Q}\) senza nessuna ipotesi, possiamo sfruttare il fatto che l’asserzione “\(\mathrm{P}\) o non \(\mathrm{P}\)” è necessariamente vera in qualunque contesto (e indipendentemente da chi sia \(\mathrm{P}\): in ciascun contesto, o \(\mathrm{P}\) è vera oppure è falsa). Quindi per dimostrare \(\models \mathrm{Q}\) ci basta considerare i due casi (\(\mathrm{P}\) vera, oppure \(\mathrm{P}\) falsa) e dimostrare che valgono
sia \(\mathrm{P}\models \mathrm{Q}\) che \(\mathrm{P}\models \mathrm{Q}\).
Se vogliamo dimostrare che una certa proprietà vale per tutti i numeri reali, possiamo considerare separatamente diversi casi (purché ogni reale sia compreso in almeno uno di essi): ad esempio possiamo trattare separatamente il caso dei reali \(< 0\) e quello dei reali \(\geq 0\).
Per ogni numero reale \(x\) si ha che \(x \leq |x|\).
Il teorema è della forma \(\models \mathrm{Q}\) con \(\underbrace{x \leq |x|}_{\mathrm{Q}}\) e vogliamo mostrare che \(\mathrm{Q}\) è vera in tutti i contesti possibili, ovvero per qualunque valore di \(x\). Siccome nella definizione di valore assoluto \[|x| = \begin{cases} x & \text{se } x \geq 0 \\ -x & \text{se } x < 0 \end{cases}\] si considerano i due casi \(\underbrace{ x < 0}_{\mathrm{P}}\) e \(\underbrace{ x ≥ 0}_{non \mathrm{P}}\), è naturale distinguere tra tali casi anche nella dimostrazione.
(Si osservi che “\(\mathrm{P}\) o non \(\mathrm{P}\)”, ovvero l’affermazione “\(x < 0 \text{ o }x \geq 0\)” , è vera per ogni numero reale \(x\), ovvero in ogni contesto che dobbiamo considerare.)
Per ogni numero reale \(x\) si ha che \(x \leq |x|\).
Distinguiamo due casi:
\(x < 0\): in questo caso \(|x| = -x\), quindi \(|x| > 0 > x\), da cui \(x \leq |x|\).
\(x \geq 0\): in questo caso \(|x| = x\), per cui vale \(x \leq |x|\).
Poiché ogni reale \(x\) o \(x < 0\) oppure \(x \geq 0\), si può allora concludere che \(x \leq |x|\) vale per ogni reale \(x\).
Riassumendo gli schemi di dimostrazione visti finora:
Dimostrazione diretta di \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\)
Si dimostra in maniera diretta che in ogni contesto in cui le ipotesi \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\) sono vere anche la tesi \(\mathrm{Q}\) risulta vera.
Dimostrazione per assurdo di \(\models\mathrm{Q}\) o di \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{Q}\)
Si assume (per assurdo) la negazione della tesi \(\mathrm{Q}\) e con un ragionamento rigoroso ne si deriva una contraddizione (eventualmente utilizzando anche le ipotesi \(\mathrm{P}_{1}\), …, \(\mathrm{P}_{n}\)).
Dimostrazione per contrapposizione di \(\mathrm{P} \models \mathrm{Q}\)
Si dimostra (in maniera diretta oppure con una delle altre tecniche di dimostrazione) il teorema non \(\mathrm{Q} \models\) non \(\mathrm{P}\).
Dimostrazione per composizione (o interpolazione) di \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n} \models \mathrm{R}\)
Si trova un enunciato \(\mathrm{Q}\) tale che \(\mathrm{P}_{1}, \dotsc, \mathrm{P}_{n}\models \mathrm{Q}\) e \(\mathrm{Q} \models \mathrm{R}\) e si “compongono” una dopo l’altra le dimostrazioni dei due teoremi.
Dimostrazione per casi di ( \(\mathrm{P}_{1}\) oppure \(\dotsc\) oppure \(\mathrm{P}_{n}) \models \mathrm{Q}\)
È sufficiente dimostrare separatamente i teoremi \(\mathrm{P}_{1} \models \mathrm{Q}\), …, \(\mathrm{P}_{n} \models \mathrm{Q}\).
Nel caso si voglia dimostrare \(\models \mathrm{Q}\) senza alcuna ipotesi è sufficiente dimostrare separatamente \(\mathrm{P}\models \mathrm{Q}\) e (non \(\mathrm{P}\)) \(\models \mathrm{Q}\) per un qualche enunciato \(\mathrm{P}\).
Le varie tecniche di dimostrazione viste possono poi essere combinate tra loro in vario modo all’interno di una stessa dimostrazione, dando luogo ad argomenti via via più complessi ma sempre logicamente corretti.
\(\sqrt{2} \notin \mathbb{Q}.\)
Notiamo che posto \(\underbrace{\sqrt{2} \notin \mathbb{Q}}_{\mathrm{Q}}\), questo è un teorema della forma \(\models\mathrm{Q}\).
Dimostrazione Supponiamo per assurdo che \(\underbrace{\text{esistano n , m} \in \mathbb{N} \setminus \left \{ 0 \right \} \text {tali che} \left (\frac{m}{n} \right )^2 = 2 }_{\text{ non } \mathrm{Q}}\) e cerchiamo di ottenere una contraddizione. Se \(n\) e \(m\) hanno \(d\) come massimo comun divisore, cioè \(n = n_{1}\cdot d\) e \(m = m_{1}\cdot d\), allora
\(\frac{m}{n} = \frac{m_{1} \cdot d}{n_{1} \cdot d} = \frac{m_{1}}{n_{1}}\),
quindi si ha che \(\left( \frac{m_{1}}{n_{1}} \right) ^2 = 2\) e che \(n_{1}\) ed \(m_{1}\) sono relativamente primi (ovvero il loro massimo comun divisore è \(1\)).
Da \[\underbrace{\text{Esistono \(m,n\) tali che }\left(\frac{m}{n} \right)^2 = 2}_{\text{ non }\mathrm{Q}}\] abbiamo quindi dedotto (in maniera diretta) l’esistenza di numeri interi \(m_{1},n_{1}\) tali che \[\underbrace{\text{\( n_{1} \) e \( m_{1} \) sono relativamente primi}}_{\mathrm{P}}\] e \[\underbrace{\left (\frac{m_{1}}{n_{1}} \right )^2 = 2 }_{\mathrm{R}}.\]
Vogliamo ora ottenere una contraddizione. Per fare questo da \(\mathrm{R}\) dedurremo \(\text{ non } \mathrm{P}\), cosicché alla fine si avrà che da non \(\mathrm{Q}\) segue
“\(\mathrm{P}\) e non \(\mathrm{P}\)”.
Siccome \(\underbrace{\left(\frac{m_{1}}{n_{1}} \right)^2 = 2}_{\mathrm{R}}\), si ha che \(\frac{m_{1}^2}{n_{1}^2} = 2\), da cui \(m_{1}^2 = 2 n_{1}^2\). Questo mostra \(m_{1}^2\) è pari, quindi, per quanto dimostrato nelle slides precedenti, \(m_{1}\) è pari, cioè è della forma \(m_{1} = 2 k\) per qualche \(k\). Quindi \(m_{1}^2 = 4 k^2\) e sostituendo questo valore nell’equazione \(m_{1}^2 = 2 n_{1}^2\) si ottiene \(4k^2 = 2n_{1}^2\), da cui \(n_{1}^2 = 2k^2\). Quindi anche \(n_{1}^2\) è pari, e per quanto visto in precedenza questo implica che \(n_{1}\) sia pari. Ma poiché sono entrambi pari, questo vuol dire che \(\underbrace{ n_{1} \text{ ed } m_{1} \text{ non sono relativamente primi}}_{\text{ non }\mathrm{P}}\), contraddizione!
La struttura della dimostrazione precedente è quindi:
Si assume (per assurdo) che la tesi del teorema \(\mathrm{Q}\) sia falsa, ovvero si assume non \(\mathrm{Q}\).
Si dimostra in maniera diretta che “non \(\mathrm{Q} \models \mathrm{P}\)”.
Si dimostra in maniera diretta che “non \(\mathrm{Q} \models \mathrm{R}\)” e “\(\mathrm{R} \models\) non \(\mathrm{P}\)”, da cui per composizione “non \(\mathrm{Q} \models\) non \(\mathrm{P}\)”.
(Si noti però che durante questa dimostrazione diretta abbiamo usato due volte il fatto che “se \(j^2\) è pari allora \(j\) è anch’esso pari”, che era stato dimostrato per contrapposizione: quindi in realtà si tratta della composizione di alcune dimostrazioni dirette, come ad esempio quella di “non \(\mathrm{Q} \models\) \(m^2\) è pari” oppure quella di “\(m\) è pari \(\models n^2\) è pari”, con la dimostrazione per contrapposizione del risultato menzionato.)
Si conclude quindi che “non \(\mathrm{Q} \models \mathrm{P}\) e non \(\mathrm{P}\)”, cosicché si è dimostrato che dall’ipotesi (assurda) non \(\mathrm{Q}\) seguirebbe una contraddizione.
Utilizzando il metodo della dimostrazione per assurdo, si conclude allora che \(\mathrm{Q}\) deve essere vera.
Dimostrazione alternativa di \(\sqrt{2} \notin \mathbb{Q}\).
Come prima, ragioniamo per assurdo. Supponiamo che esistano \(n , m \in \mathbb{N} \setminus \left \{ 0 \right \}\) tali che \(\left (\frac{m}{n} \right )^2 = 2\) (ovvero tali che \(m^2 = 2n^2\); in particolare \(\frac{m}{2} < n < m\)) e supponiamo che \(m\) sia il più piccolo numero siffatto.
Allora \(m^2\) \(=\) \(n^2 + n^2\) \(+ 2 ( m - n )^2 - k^2\), da cui (tenendo conto che \(m^2 = 2 n^2\)) si ha \(0 = 2 ( m - n )^2 - k^2\), cioè \(k^2 = 2 ( m - n )^2\), ovvero \(\left ( \frac{k}{m-n} \right)^2 = 2\).
Ma \(k\) \(= m - 2\)(\(m-n\)) \(< m\), contraddizione!
Equivalenza
Può talvolta accadere di avere due affermazioni \(\mathrm{P}\) e \(\mathrm{Q}\) tali che
\(\mathrm{P} \models \mathrm{Q}\) e \(\mathrm{Q} \models \mathrm{P}\).
Se questo accade vuol dire che in ogni contesto in cui vale \(\mathrm{P}\) deve valere anche \(\mathrm{Q}\) e, viceversa, in ogni contesto in cui vale \(\mathrm{Q}\) deve valere anche \(\mathrm{P}\); quindi \(\mathrm{P}\) e \(\mathrm{Q}\) valgono esattamente negli stessi contesti, ovvero sono equivalenti.
Scriviamo \[\mathrm{P} \equiv \mathrm{Q}\] (che si legge “\(\mathrm{P}\) e \(\mathrm{Q}\) sono logicamente equivalenti”) per dire che in ogni contesto in cui si possono valutare \(\mathrm{P}\) e \(\mathrm{Q}\)
\(\mathrm{P}\) è vera se e solo se \(\mathrm{Q}\) è vera.
In altre parole: in ogni possibile contesto, o \(\mathrm{P}\) e \(\mathrm{Q}\) sono entrambe vere, oppure sono entrambe false e sono pertanto “indistinguibili” per quel che riguarda l’essere vere o meno.
Consideriamo le seguenti affermazioni riguardanti un numero reale \(x\):
\(\mathrm{P}\): \(x \geq 0\);
\(\mathrm{Q}\): \(x= y^2\) \(y\) .
Dato un qualunque numero reale \(x\), se \(x \geq 0\) allora basta porre \(y= \sqrt{x}\) per avere \(x = y^2\). Quindi
\(\mathrm{P}\) \(\models\) \(\mathrm{Q}\).
D’altra parte, se \(x = y^2\) per qualche numero reale \(y\) allora \(x \geq 0\) perché il quadrato di un numero reale è sempre un numero non negativo. Quindi
\(\mathrm{Q}\) \(\models\) \(\mathrm{P}\).
Abbiamo perciò verificato che per ogni possibile valore di \(x\), la proprietà \(\mathrm{P}\) è vera se e solo se \(\mathrm{Q}\) è vera. Questo vuole dire che \(\mathrm{P}\) e \(\mathrm{Q}\) sono affermazioni equivalenti, ovvero
\(\mathrm{P} \equiv \mathrm{Q}\).
Alcune proprietà fondamentali di \(\models\) ed \(\equiv\)
Vediamo infine alcune proprietà di base dei concetti appena introdotti. Alcune di esse sono ovvie, ma è bene comunque tenerle a mente perché torneranno utili in seguito.
Date tre affermazioni \(\mathrm{P}\), \(\mathrm{Q}\) ed \(\mathrm{R}\) qualsiasi, si ha che
\(\mathrm{P} \models \mathrm{P}\) (Riflessività)
se \(\mathrm{P} \models \mathrm{Q}\) e \(\mathrm{Q} \models \mathrm{R}\), allora \(\mathrm{P} \models \mathrm{R}\) (Transitività)
La prima proprietà è del tutto ovvia. La seconda segue dal fatto che \(\mathrm{P} \models \mathrm{R}\) può essere dimostrato componendo le dimostrazioni di \(\mathrm{P} \models \mathrm{Q}\) e \(\mathrm{Q} \models \mathrm{R}\) (dimostrazione per composizione o interpolazione).
Date tre affermazioni \(\mathrm{P}\), \(\mathrm{Q}\) ed \(\mathrm{R}\) qualsiasi, si ha che
\(\mathrm{P} \equiv \mathrm{P}\) (Riflessività)
se \(\mathrm{P} \equiv \mathrm{Q}\) allora anche \(\mathrm{Q} \equiv \mathrm{P}\) (Simmetria)
se \(\mathrm{P} \equiv \mathrm{Q}\) e \(\mathrm{Q} \equiv \mathrm{R}\), allora \(\mathrm{P} \equiv \mathrm{R}\) (Transitività)
La prima e la seconda proprietà sono del tutto ovvie. La terza segue dalla transitività di \(\models\). Infatti, se \(\mathrm{P} \equiv \mathrm{Q}\) e \(\mathrm{Q} \equiv \mathrm{R}\), allora in particolare \(\mathrm{P} \models \mathrm{Q}\) e \(\mathrm{Q} \models \mathrm{R}\), da cui \(\mathrm{P} \models \mathrm{R}\) per la transitività di \(\models\). Viceversa, da \(\mathrm{P} \equiv \mathrm{Q}\) e \(\mathrm{Q} \equiv \mathrm{R}\) segue anche che \(\mathrm{Q} \models \mathrm{P}\) e \(\mathrm{R} \models \mathrm{Q}\), da cui \(\mathrm{R} \models \mathrm{P}\) sempre per transitività di \(\models\). Quindi \(\mathrm{P} \equiv \mathrm{R}\).